public class ReverseLinkedList {
    /*
    * 反转链表
    * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    * */
    public static void main(String[] args) {

    }

    // 定义一个新的链表，费内存
    public ListNode mySolution(ListNode head) {
        if(head == null)
            return null;
        ListNode result = null;
        while (head.next != null){
            ListNode node = new ListNode(head.val, result);
            result = node;
            head = head.next;
        }
        ListNode node = new ListNode(head.val, result);
        return node;
    }

    // 反转指针,不用新建链表
    public ListNode solution(ListNode head) {
        if(head == null)
            return null;
        ListNode preNode = head.next;
        head.next = null;
        ListNode flag;
        while (preNode != null){
            // 留下能找到原链表的点
            flag = preNode.next;
            // 反转指针
            preNode.next = head;
            // 指向下一组
            head = preNode;
            preNode = flag;
        }
        return head;

    }
}
